#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
struct node
{
int v;
int i;
struct node* next;
}*s,*e;



void print()
     {
     struct node*n=s;
	 while(n!=NULL)
       { printf("%d ",n->v);
	   n=n->next;
	   }
    }

void count(int x)
{struct node*i;int c=0;
for(i=s;i!=NULL;i=i->next)
{if(i->v==x)
{c++;}

}
printf("\nThe no. of times %d occured is %d\n",x,c);
}

void append (int m)
     {
     struct node *n= malloc(sizeof(struct node));
     n->v=m;
     n->next=NULL;
     if(s==e)
             {
              s=e=n;}
     else
         {    
         e->next=n;
         e=n;
         }
         printf("\nThe node with value %d is appended\nThe list now is:-\n",n->v);
         print();
         }

int len()
{
int c=0;
struct node*i;
for (i=s;i!=NULL;i=i->next)
{c++;
}
return c;
}

void insert(struct node*n,int pos)
     {
     struct node * pre,*cur;

     if(pos>len()|| pos<0)

     {   printf("\nPosition is greater than length \n");
	 return;
	 }
  else if(pos==0)
       { s->next=n;
         s=n;
             }
             for(cur=s;cur->i<pos-1;pre=cur,cur=cur->next);
/*{
if(cur->i==pos)
{  n->i=pos;
pre->next=n;
n->next=cur;
} */
//break;
        struct node * temp = pre->next;
               pre->next=n;
               n->next=temp;

                 n->i=pos;
                 for(cur=n->next;cur!=NULL;cur=cur->next)
                 {	cur->i=(cur->i)+1;
                 }

			printf("\nThe list is:-\n") ;
	        print();
            }




/*void remove (int i)
{
     struct node * pre,*cur;
     int pos;
     if (i>len()||i<0)
    {printf("\nInvalid position\n");
     for (pre=NULL,cur=s;cur!=NULL;pre=cur,cur=cur->next)
     {   if(cur->v ==i )
          { pos=(cur->i);
                      pre->next=cur->next;
             free(cur);       }
         }
         for (cur=s;cur!=NULL;cur=cur->next)
         {
             if(cur->i==pos)
             { while(cur!=NULL)
              {cur->i-=1;
              cur=cur->next;
              }
             break;
             
         }
         }
     }
*/
void reverse()
{
struct node *n,*t,*m;
n=NULL;      m=s;
while(m!=NULL)
{t=n;
n=m;
m=m->next;
n->next=t;
}
printf("The list's reverse is:-\n") ;
while(n!=NULL)
{
printf("%d",n->v);
n=n->next;
}
}


void sort()
               
          { struct node *a = NULL;
            struct node *b = NULL;
            struct node *c = NULL;
            struct node *d = NULL;
            struct node *tmp = NULL;
            struct node* s1=s;
 a = c = s1;
 while(a->next != NULL) {
  d = b = a->next;
  while(b != NULL) {
   if(a->v > b->v) {
     if(a->next == b) { 
     if(a == s1) {
      a->next = b->next;
      b->next = a;
      tmp = a;
      a = b;
      b = tmp;
      s1 = a;
      c = a;
      d = b;
      b = b->next;
     } else {
      a->next = b->next;
      b->next = a;
      c->next = b;
      tmp = a;
      a = b;
      b = tmp;
      d = b;
      b = b->next;
     }
    } else {
     if(a == s1) {
      tmp = b->next;
      b->next = a->next;
      a->next = tmp;
      d->next = a;
      tmp = a;
      a = b;
      b = tmp;
      d = b;
      b = b->next;
      s1 = a;
    } else {
     tmp = b->next;
     b->next = a->next;
     a->next = tmp;
     c->next = b;
     d->next = a;
     tmp = a;
     a = b;
     b = tmp;
     d = b;
     b = b->next;
    }
   }
  } else {
   d = b;
   b = b->next;
  }
 }
  c = a;
  a = a->next;
 }
}

void pop(int i = -1)
{struct node *i*t;int v=0;
if (i==-1)
{
for(i=s;i!=NULL;i=i->next);
t=i;
v=t->v;
i=i->next;
free(t);}

else
{
  struct node * pre,*cur;
     int pos;
     if (i>len())
    {printf("\nInvalid position\n");
     for (pre=NULL,cur=s;cur!=NULL;pre=cur,cur=cur->next)
     {   if(cur->i ==i )
          { pos=(cur->i);
                      pre->next=cur->next;
             free(cur); v=cur->v; break;     }
         }
         for (cur=s;cur!=NULL;cur=cur->next)
         {
             if(cur->i==pos)
             { while(cur!=NULL)
              {cur->i-=1;
              cur=cur->next;
              }
             break;
             
         }
         }return v}

int index(int i=0)
{
for (i=s;i!=NULL;i=i->next)
{
if(i->v==i)
{
returni->i;
}
}
}




void extend()
{struct node *s1,*e1,*n,*i;int v;s1=e1;
while(v!=0)
{n=malloc(sizeof(struct node))
printf("\nEnter the new list to extend the previous one(0 to exit)\n ");
scanf("%d",&v);
if(v==0)
{break;}
else{
n->v=v;
n->next=NULL;
e1->next=n;
e1=n;
}
for(i=s;i!=NULL;i=i->next);
i->next=s1;
i=s1;

}











int main()
{
int i=0,c=0,ct=0,l;

struct node*j;
while (1)
{
printf("\n...LIST OPERATIONS...\n\t0 Exit\n\t1.Enter the elements in the list \n\t2.Append\n\t3.Reverse \n\t4.Insert\n\t5.Remove\n\t6. Sort\n\t7. Pop \n\t8.Count\n\t9.Index\n\t10.Extend");
scanf("%d",&c);
switch (c)
{
case 0:
{
return 0;
break;
}
case 1:
{
char c='y';
	while(c=='y')
{	struct node*n = malloc(sizeof( struct node));
	printf("Enter the value of the node:\n");
	scanf("%d",&n->v);

	n->next=NULL;

	if(s==NULL)
	{s=e=n;}
	else
	{
	e->next=n;
	e =n;
	}

printf("The list is:\n");print();
printf("\n Want to Enter more (y/n)");
scanf("%s",&c);
if (c!='y')
{  for (j=s;j!=NULL;j=j->next)
		{
		n->i=ct;
				ct++;
		}
}
}
break;}

case 2: {
printf("\nEnter the value to be appended\n");
scanf("%d",&i);
append(i);
break;   }

case 3:
{
reverse();
break;
}
case 4:{
	  int v;
struct node* o=malloc(sizeof( struct node));
printf("\nEnter the value of the node to insert\n");
scanf("%d",&v);o->v=v;
o->next=NULL;
printf("\nEnter the position \n ");
scanf("%d",&i);
insert(o,i);break;
}

case 5:{printf("\nEnter the value to remove\n");scanf("%d",&i); 
     remove(i); break;}
case 6:{sort();print();break;}
case 7:{printf("\nEnter the position of node  to be popped\n");scanf("%d",&i);l=pop(i);if(l==0){printf("\nValue doesnt exist\n");}else{printf
("Value popped is %d",l);}
break;}
case 8:{printf("\nEnter the value to be counted\n");scanf("%d",&i);count(i);break;}
case 9:{printf("\nEnter the value whose index is to be found\n");scanf("%d",&i);l=ind(i);
if(!i){printf("\nError!!! \nno such value\n");}
else{printf("\nThe index of (first) %d  is %d\n",i,l);
}
break;
}

case 10: {extend();break;}     
}
}
}
